package com.leetcode.partition8;

import java.io.*;
import java.util.*;

/**
 * @author `RKC`
 * @date 2021/12/30 15:16
 */
public class LC752打开转盘锁AStar {

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] deadends = reader.readLine().split("\\s+");
        String target = reader.readLine();
        writer.write(openLock(deadends, target) + "\n");
        writer.flush();
    }

    public static int openLock(String[] deadends, String target) {
        Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
        String start = "0000";
        if (start.equals(target)) return 0;
        if (deadSet.contains(target) || deadSet.contains(start)) return -1;
        return aStar(deadSet, start, target);
    }

    private static int aStar(Set<String> deadSet, String start, String end) {
        Map<String, Integer> distMap = new HashMap<>();
        PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.val, o2.val));
        distMap.put(start, 0);
        heap.add(new Node(eval(start, end), start));
        while (!heap.isEmpty()) {
            Node curr = heap.poll();
            int dis = distMap.get(curr.state);
            if (curr.state.equals(end)) return dis;
            char[] currState = curr.state.toCharArray();
            for (int i = 0; i < currState.length; i++) {
                for (int j = -1; j <= 1; j += 2) {
                    char ch = currState[i];
                    //将字符ch进行旋转
                    int n = ch - '0', next = (n + j) % 10;
                    if (next == -1) next = 9;
                    currState[i] = (char) (next + '0');
                    String nextState = new String(currState);
                    //只有没被锁才可以进行转移
                    if (!deadSet.contains(nextState) && (!distMap.containsKey(nextState) || distMap.get(nextState) > dis + 1)) {
                        distMap.put(nextState, dis + 1);
                        heap.add(new Node(eval(nextState, end) + dis + 1, nextState));
                    }
                    currState[i] = ch;
                }
            }
        }
        return -1;
    }

    private static int eval(String state, String end) {
        int res = 0;
        for (int i = 0; i < state.length(); i++) {
            int a = state.charAt(i) - '0', b = end.charAt(i) - '0';
            int c = Math.max(a, b), d = Math.min(a, b);
            //在正向转和反向转中找最小的
            res += Math.min(c - d, d + 10 - c);
        }
        return res;
    }

    private static class Node {
        private int val;
        private String state;

        public Node(int val, String state) {
            this.val = val;
            this.state = state;
        }
    }
}
